#include <iostream>
#include <string>
#include <stack>

using namespace std;

enum push_drct {
    LEFT, RIGHT
};

class tree_node {
public:
    string str;
    tree_node *left = nullptr;
    tree_node *right = nullptr;
    enum push_drct drct = LEFT;

    tree_node(const string &str) {
        this->str = str;
    }
};

using trav_cb = void (tree_node*);

tree_node* init_tree() {
    cout << "tree diagam:" << endl;
    cout << "   A" << endl;
    cout << "  / \\" << endl;
    cout << " B   C" << endl;
    cout << "/ \\ / \\" << endl;
    cout << "D E F G" << endl;

    tree_node *root = new tree_node("A");
    root->left = new tree_node("B");
    root->right = new tree_node("C");

    root->left->left = new tree_node("D");
    root->left->right = new tree_node("E");

    root->right->left = new tree_node("F");
    root->right->right = new tree_node("G");

    return root;
}

void nlr_trav(tree_node *tree, trav_cb cb) {
    stack<tree_node*> node_stack = stack<tree_node*>();

    tree_node *cur = tree;
    while (node_stack.size() > 0 || cur != nullptr) {
        if (cur != nullptr) {
            cb(cur);
            node_stack.push(cur);
            cur = cur->left;
        } else {
            cur = node_stack.top();
            node_stack.pop();
            cur = cur->right;
        }
    }
}

void lnr_trav(tree_node *tree, trav_cb cb) {
    stack<tree_node*> node_stack = stack<tree_node*>();

    tree_node *cur = tree;
    while (node_stack.size() > 0 || cur != nullptr) {
        if (cur != nullptr) {
            node_stack.push(cur);
            cur = cur->left;
        } else {
            cur = node_stack.top();
            cb(cur);
            node_stack.pop();
            cur = cur->right;
        }
    }
}

void lrn_trav(tree_node *tree, trav_cb cb) {
    stack<tree_node*> node_stack = stack<tree_node*>();

    tree_node *cur = tree;
    while (node_stack.size() > 0 || cur != nullptr) {
        if (cur != nullptr) {
            cur->drct = LEFT;
            node_stack.push(cur);
            cur = cur->left;
        } else {
            cur = node_stack.top();

            if (cur->drct == LEFT) {
                cur->drct = RIGHT;
                cur = cur->right;
            } else {
                cb(cur);
                node_stack.pop();
                cur = nullptr;
            }
        }
    }
}

void free_tree(tree_node *tree) {
    lrn_trav(tree, [](tree_node *n) -> void { delete n; });
}

int main(int argc, char *argv[]) {
    tree_node *cur = init_tree();

    auto print_node = [](tree_node *cur) -> void { 
        cout << cur->str << endl;
    };

    cout << "NLR traverse: " << endl;
    nlr_trav(cur, print_node);
    cout << "LNR traverse: " << endl;
    lnr_trav(cur, print_node);
    cout << "LRN traverse: " << endl;
    lrn_trav(cur, print_node);

    free_tree(cur);
}

